'''
Created on 18 avr. 12

@author: peterd
'''

class CalculationError:
	pass


def get_1d_cutting_plan(stock_piece_length, custom_pieces, cut_thickness):
	num_custom_pieces = len(custom_pieces)	
	cutting_schema = {}	
	i = 0
	
	while i < num_custom_pieces:
		num_elem = 1	
		prev_custom_packs = []
		while num_elem <= num_custom_pieces - i:
			k = num_elem - 1			
			n_elem_custom_packs = []
			custom_pack = []
	
			if num_elem == 1:
				custom_pack.append((i + k, custom_pieces[i + k]))
				n_elem_custom_packs.append(custom_pack)
				# TODO: move to function
				custom_pack_waste = stock_piece_length - custom_pieces[i + k]
				if cutting_schema.has_key(custom_pack_waste):
					if custom_pack not in cutting_schema[custom_pack_waste]:
						cutting_schema[custom_pack_waste].append(custom_pack)
				else:
					cutting_schema[custom_pack_waste] = [custom_pack]			
			else:
				for prev_custom_pack in prev_custom_packs:
					l = k
					while l < num_custom_pieces:
						custom_pack = list(prev_custom_pack)
						custom_pack_used_length = 0
						for custom_piece in custom_pack:
							custom_pack_used_length = custom_pack_used_length + custom_piece[1] 		
						n = l		
						if i + n < num_custom_pieces:
							while len(custom_pack) < num_elem:	
								try:	
									if custom_pack_used_length + custom_pieces[i + n] > stock_piece_length:
										break
								except IndexError:
									pass
								custom_pack.append((i + n, custom_pieces[i + n]))
								custom_pack_used_length = custom_pack_used_length + custom_pieces[i + n]
								n = n + 1
								if i + n == num_custom_pieces:
									break
							n_elem_custom_packs.append(custom_pack)
							custom_pack_waste = stock_piece_length - custom_pack_used_length
							# TODO: move to function
							if cutting_schema.has_key(custom_pack_waste):
								if custom_pack not in cutting_schema[custom_pack_waste]:
									cutting_schema[custom_pack_waste].append(custom_pack)
							else:
								cutting_schema[custom_pack_waste] = [custom_pack]
						l = l + 1
					k = k + 1
									
			num_elem = num_elem + 1		
			prev_custom_packs = list(n_elem_custom_packs)
		i = i + 1
		
	custom_pieces_ids = []
	bestfit_cutting_schema = {}
	
	for waste in sorted(cutting_schema.iterkeys()):
		for custom_pack in cutting_schema[waste]:
			already_packed = False		
			for custom_piece in custom_pack:
				custom_piece_id = custom_piece[0] 
				if custom_piece_id in custom_pieces_ids:
					already_packed = True
					break
			if not already_packed:			
				custom_piece_lengths = []
				custom_pack_length = 0
				for custom_piece in custom_pack:
					custom_piece_id = custom_piece[0]
					custom_piece_length = custom_piece[1]
					custom_pieces_ids.append(custom_piece_id)
					# use remaining length from any of the previous schemas if possible
					reused_bestfit_custom_pack = []
					remaining_waste = 0
					for bestfit_waste in sorted(bestfit_cutting_schema.iterkeys()):
						i = 0
						for bestfit_custom_pack in bestfit_cutting_schema[bestfit_waste]:
							if custom_piece_length <= bestfit_waste:
								bestfit_custom_pack.append(custom_piece_length)
								reused_bestfit_custom_pack = list(bestfit_custom_pack)
								remaining_waste = bestfit_waste - custom_piece_length
								waste = waste + custom_piece_length 
								break
							i = i + 1
						if reused_bestfit_custom_pack:
							break
					
					if not reused_bestfit_custom_pack:					
						custom_piece_lengths.append(custom_piece_length)
						custom_pack_length = custom_pack_length + custom_piece_length
					else:
						custom_packs = bestfit_cutting_schema[bestfit_waste]
						if len(custom_packs) == 1:
							del bestfit_cutting_schema[bestfit_waste]
						else:
							del bestfit_cutting_schema[bestfit_waste][i]
		
						if bestfit_cutting_schema.has_key(remaining_waste):
							bestfit_cutting_schema[remaining_waste].append(reused_bestfit_custom_pack)
						else:
							bestfit_cutting_schema[remaining_waste] = [reused_bestfit_custom_pack]
							
						
										
				if custom_piece_lengths:
					if bestfit_cutting_schema.has_key(waste):
						bestfit_cutting_schema[waste].append(custom_piece_lengths)
					else:
						bestfit_cutting_schema[waste] = [custom_piece_lengths]
		
	if len(custom_pieces_ids) != num_custom_pieces:
		raise CalculationError()

	cutting_plan = {'schema': [] }
	i = 1
	total_waste = 0
	for bestfit_waste in sorted(bestfit_cutting_schema.iterkeys()):
		for bestfit_custom_pack in bestfit_cutting_schema[bestfit_waste]:
			augmented_custom_pack = []
			for piece in bestfit_custom_pack:
				if piece == stock_piece_length:
					augmented_custom_pack.append(piece)
				else:
					augmented_custom_pack.append(piece - cut_thickness)					
			cutting_plan['schema'].append({'id': i, 'pack': augmented_custom_pack, 'waste': bestfit_waste})
			total_waste = total_waste + bestfit_waste
			i = i + 1 		
	cutting_plan['total_stock_num'] = i - 1			
	cutting_plan['total_waste'] = total_waste

	return cutting_plan








